#include "priority_queue.hpp"
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <functional>
#include <algorithm>
#include <unordered_map>
using namespace std;


class Solution 
{
public:

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 模板参数在实例化时必须是一个确定的类型，而lambda表达式的类型是一个匿名类型，通常无法直接作为模板参数。
        // 使用function,或者bind试试
        // priority默认是大堆，使用 <
        auto Greate = []( pair< string,int>& p1, pair< string,int>& p2) 
                        {
                            if(p1.second != p2.second)
                                return p1.second > p2.second;
                            else
                                return p1.first < p2.first;
                        }; 
        // 不能使用pair<const string,int>，priority内部元素需要支持移动构造和移动赋值
        // <>内部是类型，lambda表达式是函数对象并不是类型
        // priority_queue<pair< string,int>, vector<pair< string,int>>, function<bool( pair< string,int>& p1, pair<  string,int>& p2)>> pq(Greate);
        // 使用c++11关键字 decltype获取lambda表达式的类型
        my_priority_queue::priority_queue<pair< string,int>, vector<pair< string,int>>, decltype(Greate)> pq(Greate);

        // 统计字符串出现的频次
        unordered_map<string,int> hash;
        for(auto& str : words)
            hash[str]++;
        
        // 构建topK
        for(auto& it : hash)
        {
            pq.push(it);
            if(pq.size() > k)
            {
                pq.pop();
            }
        }
        vector<string> res;
        while(!pq.empty())
        {
            res.push_back(pq.top().first);
            pq.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

int test()
{
    vector<string> vs({"i", "love", "leetcode", "i", "love", "coding"});
    Solution s;
    auto res = s.topKFrequent(vs,4);
    for(auto& str : res)
    {
        cout << str << endl;
    }

    return 0;
}
int main()
{
    test();
	// vector<int> v({ 4, 3, 6, 7, 2, 8, 9, 5 });
	// my_priority_queue::priority_queue<int> pq(v.begin(), v.end());
	// cout << pq.top() << endl;
	// pq.pop();
	// pq.push(19);
	// pq.push(19);
	// pq.push(14);
	// pq.push(13);
	// pq.push(20);

	// while (!pq.empty())
	// {
	// 	cout << pq.top() << endl;
	// 	pq.pop();
	// }
	
	return 0;
}